package org.example.myleet.pointer;

import org.example.myleet.Utils.Assert;
import org.example.myleet.Utils.JsonUtils;
import org.example.myleet.Utils.ListNode;

import java.util.*;

public class MultiPointerSolution {

    //面试题 01.05. 一次编辑
    public boolean oneEditAway(String first, String second) {
        if (first.length() == second.length()) {
            int editCount = 0;
            for (int i = 0; i < first.length(); ++i) {
                if (first.charAt(i) != second.charAt(i)) {
                    ++editCount;
                }
            }
            return editCount < 2;
        }
        if (second.length() > first.length()) {
            return oneEditAway(second, first);
        }
        if (first.length() - second.length() > 1) {
            return false;
        }
        int l1 = 0, r1 = first.length() - 1, l2 = 0, r2 = second.length() - 1;
        while (l2 <= r2) {
            if (first.charAt(l1) == second.charAt(l2)) {
                ++l1;
                ++l2;
            } else if (first.charAt(r1) == second.charAt(r2)) {
                --r1;
                --r2;
            } else {
                return false;
            }
        }
        return true;
    }

    //面试题 17.11. 单词距离
    public int findClosest(String[] words, String word1, String word2) {
        int minGap = Integer.MAX_VALUE;
        Integer prevI1 = null, prevI2 = null;
        int hashCode1 = word1.hashCode(), hashCode2 = word2.hashCode();
        for (int i = 0; i < words.length; ++i) {
            int wordHashCode = words[i].hashCode();
            if (wordHashCode == hashCode1) {
                if (null != prevI2) {
                    minGap = Math.min(minGap, Math.abs(i - prevI2));
                }
                prevI1 = i;
            } else if (wordHashCode == hashCode2) {
                if (null != prevI1) {
                    minGap = Math.min(minGap, Math.abs(i - prevI1));
                }
                prevI2 = i;
            }
        }
        return minGap;
    }

    //p19
    /**
     * 双指针法，快指针先走n步，然后快慢指针一起走，直到快指针到达最后一个节点（此时fast.next == null）
     * 此时慢指针即为倒数n位节点的左节点，轻松做删除
     * 考虑特殊情况，只有1的长度
     * 0ms
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode fast = head, slow = head;
        int len = 0;
        for (int i=0; i<n; i++) {
            //快指针先走n步
            fast = fast.next;
            ++len;
        }
        if (1 == len && null == fast) {
            //特殊情况，链表长度位1，删除后相当于null
            return null;
        }
        if (null == fast) {
            //特殊情况，相当于n = len，倒数第n个节点即第一个节点head，移除head相当于直接返回第二个节点
            return head.next;
        }
        while (fast.next != null) {
            //快慢指针一起走
            fast = fast.next;
            slow = slow.next;
        }
        //删除倒数第n个节点
        slow.next = slow.next.next;
        return head;
    }

    //剑指Offer 22
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode fast = head;
        for (int i = 0; i < k; ++i) {
            fast = fast.next;
            if (fast == null) {
                break;
            }
        }
        ListNode slow = head;
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

    //p26
    /**
     * 0 ms
     * 双指针，slow指向待放入数据的位置，代表实际数组长度；fast则代表数组遍历的位置
     * 0(n)
     */
    public int removeDuplicates(int[] nums) {
        int len = nums.length;
        if (len < 1) {
            return 0;
        }
        int slow = 1, fast = 1, repeat = nums[0], n;
        while (fast < len) {
            n = nums[fast];
            if (n != repeat) {
                nums[slow++] = n;
                repeat = n;
            }
            ++fast;
        }
        return slow;
    }

    //p27
    /**
     * 0 ms
     * 原地算法 + 双指针，慢指针是实际数组位置，快指针遍历数组，与val值相同则放弃
     */
    public int removeElement(int[] nums, int val) {
        int slow = 0, fast = 0;
        while (fast < nums.length) {
            if (nums[fast] != val) {
                nums[slow++] = nums[fast];
            }
            ++fast;
        }
        return slow;
    }

    //剑指Offer 52
    /**
     * 思路：
     * 题目要求一定会有交点的，而且交点之后的所有节点是相同的，要求时间复杂度O(n)，空间复杂度O(1)
     * 则要求只是通过遍历完成查找，并且使用固定的变量记录必要的信息
     * 于是想到先找到两个链表的长度，然后剔除掉较长的长出来的部分，站在同一起跑线上观察两条链上的节点是否"相同"
     * ！这道题的一个坑点是两条链上的节点是否"相同"，比较的不是节点的值，而是节点的指针
     */
    public class Solution {
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            if (headA == null || headB == null) {
                return null;
            }
            int la = 0;
            ListNode da = new ListNode(-1), curA = da, tailA = null;
            da.next = headA;
            while (curA.next != null) {
                curA = curA.next;
                tailA = curA;
                ++la;
            }
            int lb = 0;
            ListNode db = new ListNode(-1), curB = db, tailB = null;
            db.next = headB;
            while (curB.next != null) {
                curB = curB.next;
                tailB = curB;
                ++lb;
            }
            if (tailA.val != tailB.val) {
                return null;
            }
            if (la > lb) {
                for (int i = 0; i < la - lb; ++i) {
                    da.next = da.next.next;
                }
            } else if (la < lb) {
                for (int i = 0; i < lb - la; ++i) {
                    db.next = db.next.next;
                }
            }
            curA = da;
            curB = db;
            while (curA.next != null) {
                if (curA.next == curB.next) {
                    return new ListNode(curA.next.val);
                }
                curA = curA.next;
                curB = curB.next;
            }
            return null;
        }
    }

    /**
     * 61【双指针】旋转链表
     * 0 ms
     */
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null) {
            return null;
        }
        //先通过遍历计算链表长度
        int n = 0;
        ListNode curNode = head, tail = head;
        while (curNode != null) {
            ++n;
            tail = curNode;
            curNode = curNode.next;
        }
        //得出真实需要翻转的trueK次
        int trueK = k >= n ? (k % n) : k;
        if (trueK == 0) {
            return head;
        }
        ListNode dummyHead = new ListNode(0);
        curNode = head;
        int prev = n - trueK - 1;
        for (int i=0; i<prev; ++i) {
            //直至取得curNode为截断点，curNode.next截出来用来连接到原头部
            curNode = curNode.next;
        }
        //截断并重新连接
        tail.next = head;
        dummyHead.next = curNode.next;
        curNode.next = null;
        return dummyHead.next;
    }

    /**
     * 83【链表指针，链表操作】删除排序链表中的重复元素
     * 0 ms
     * 链表操作
     */
    public ListNode deleteDuplicates83(ListNode head) {
        if (null == head) {
            return null;
        }
        //curNode - 当前指向的节点，dummyHead - 挂载head的伪头，用于返回结果用
        ListNode curNode = head, dummyHead = new ListNode(0);
        dummyHead.next = head;
        while (curNode.next != null) {
            if (curNode.val == curNode.next.val) {
                //如果当前节点的值是重复值，则一直移除节点直到没有相同节点
                while (curNode.next != null && curNode.val == curNode.next.val) {
                    curNode.next = curNode.next.next;
                }
            } else {
                curNode = curNode.next;
            }
        }
        return dummyHead.next;
    }

    /**
     * 82【三指针】删除排序链表中的重复元素 II
     * 链表操作，删除节点过程
     */
    public ListNode deleteDuplicates(ListNode head) {
        if (null == head) return head;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        //利用3个指针进行检查
        ListNode prev = dummy, curr = head, next = curr.next;
        while (null != next) {
            if (curr.val == next.val) {
                //如果出现curr.val == next.val，说明出现重复，逐个重复的删除
                while (null != next && curr.val == next.val) {
                    //删除与curr重复的next
                    curr.next = next.next;
                    next = next.next;
                }
                //最后删除掉curr
                prev.next = curr.next;
            } else {
                //没有发现重复，链表不变，prev往前移动
                prev = curr;
            }
            //剩下2个指针也向前移动
            curr = curr.next;
            next = null != curr ? curr.next : null;
        }
        return dummy.next;
    }

    /**
     * 160【双指针】相交链表
     * 官方解，非常巧妙的双指针利用，pA指针从headA开始，pB指针从headB开始
     * 当pA指针到达链表结尾时，移到headB继续；当pB指针到达链表结尾时，移到headA继续
     * 这样操作，如果存在链表相交的情况，pA和pB在走过相同的路程后会汇集到同一个节点上
     * 如果不相交，则pA和pB在走过相同的路程（lenA+lenB）后会同时到达链表结尾，此时均指向null，结束
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (null == headA || null == headB) return null;
        ListNode pA = headA, pB = headB;
        while (pA != pB) {
            ListNode pAn = pA.next;
            ListNode pBn = pB.next;
            if (pAn == null && pBn == null) return null;
            if (pAn == null) pAn = headB;
            if (pBn == null) pBn = headA;
            pA = pAn;
            pB = pBn;
        }
        return pA;
    }

    /**
     * 167 【双指针】两数之和 II - 输入有序数组
     * 双指针
     * 需要证明正确性
     * 首先需要数组是非递减的，非递减保证numbers[l] <= numbers[r]总是成立
     * 在两边收缩过程中，两个指针对应的数字之和超过target时，说明右边的数太大，所以右指针向左收缩
     * 如果两个指针对应的数字之和小于target时，说明左边的数太小，所以左指针向右扩张
     * 如果题目有解，则最终一定会通过这样的微调到达目标结果
     */
    public int[] twoSum(int[] numbers, int target) {
        int l = 0, r = numbers.length - 1;
        while (r > l) {
            int sum = numbers[l] + numbers[r];
            if (sum > target) {
                --r;
            } else if (sum < target) {
                ++l;
            } else {
                return new int[]{l + 1, r + 1};
            }
        }
        return new int[]{l + 1, r + 1};
    }

    /**
     * 324【桶排序+双指针】摆动排序 II
     */
    public void wiggleSort(int[] nums) {
        int BOUND = 5001;
        int[] arr = nums.clone();
        int n = nums.length;
        //桶排序
        int[] numCount = new int[BOUND];
        for (int num : arr) {
            ++numCount[num];
        }
        int i = 0, j = 0, k;
        while (j < BOUND) {
            while (j < BOUND && numCount[j] == 0) {
                ++j;
            }
            if (j < BOUND) {
                arr[i++] = j;
                --numCount[j];
            }
        }
        //利用双指针交换前后两半的数字使之形成交错
        int x = (n + 1) / 2;
        for (i = 0, j = x - 1, k = n - 1; i < n; i += 2, j--, k--) {
            nums[i] = arr[j];
            if (i + 1 < n) {
                nums[i + 1] = arr[k];
            }
        }
    }

    /**
     * 344【双指针+原地算法】反转字符串
     */
    public void reverseString(char[] s) {
        int l = 0, r = s.length - 1;
        while (l < r) {
            char c = s[l];
            s[l] = s[r];
            s[r] = c;
            ++l;
            --r;
        }
    }

    /**
     * 345【双指针】反转字符串中的元音字母
     * 对向移动的双指针
     */
    public String reverseVowels(String s) {
        //注意题目没说大写字母不考虑
        char[] vowels = new char[]{'a', 'A', 'e', 'E', 'i', 'I', 'o', 'O', 'u', 'U'};
        char[] charArr = s.toCharArray();
        int len = charArr.length;
        int l = 0, r = s.length() - 1;
        while (l < r) {
            while (l < len && l < r && nonVowel(charArr[l], vowels)) {
                ++l;
            }
            while (r > 0 && r > l && nonVowel(charArr[r], vowels)) {
                --r;
            }
            if (nonVowel(charArr[l], vowels) || nonVowel(charArr[r], vowels)) {
                break;
            }
            char t = charArr[l];
            charArr[l] = charArr[r];
            charArr[r] = t;
            ++l;
            --r;
        }
        return new String(charArr);
    }
    private boolean nonVowel(char c, char[] vowels) {
        for (char v : vowels) {
            if (c == v) {
                return false;
            }
        }
        return true;
    }

    //p792
    public int numMatchingSubseq(String s, String[] words) {
        int n = words.length;
        Queue<int[]>[] queueArr = new Queue[26];
        for (int i = 0; i < 26; ++i) {
            queueArr[i] = new LinkedList<>();
        }
        for (int j = 0; j < n; ++j) {
            char ch = words[j].charAt(0);
            queueArr[ch - 'a'].offer(new int[]{j, 0});
        }
        int result = 0;
        for (int i = 0; i < s.length(); ++i) {
            char ch = s.charAt(i);
            Queue<int[]> queue = queueArr[ch - 'a'];
            int len = queue.size();
            for (int j = 0; j < len; ++j) {
                int[] match = queue.poll();
                int newIdx = match[1] + 1;
                if (newIdx < words[match[0]].length()) {
                    char c = words[match[0]].charAt(newIdx);
                    queueArr[c - 'a'].offer(new int[]{match[0], newIdx});
                } else {
                    ++result;
                }
            }
        }
        return result;
    }

    //p795
    public int numSubarrayBoundedMax(int[] nums, int left, int right) {
        int l = 0, n = nums.length;
        //从复合区间内的值开始
        while (l < n && nums[l] > right) {
            ++l;
        }
        int r = l, result = 0;
        while (r < n) {
            if (nums[r] > right) {
                //找到一个右指针超出区间的位置，被这个值分割出一个计数区间，计算区间产生的有效子数组
                long increase = calIncrease(nums, left, l, r);
                //累积到结果中
                result += increase;
                //跳过r这个位置，从r的下一个位置重新找区间
                l = r + 1;
                r = l;
            } else {
                ++r;
            }
        }
        //遍历结束，需要再计算一次最后一块区间的结果
        long increase = calIncrease(nums, left, l, r);
        result += increase;
        return result;
    }

    private long calIncrease(int[] nums, int left, int l, int r) {
        //m-区间的数组长度
        long m = r - l;
        //需要剔除的子数组，因为有些元素低于left，由其单独产生的子数组需要被剔除
        long exclude = 0;
        for (int i = l; i < r; ++i) {
            if (nums[i] < left) {
                //找到低于left的元素，一直往右边找找到一块完整的低于left的区间，则这块区间产生的子数组需要被剔除
                int s = i, e = i;
                do {
                    ++e;
                    ++i;
                } while (i < r && nums[i] < left);
                --i;
                //计算被剔除的子数组总数
                exclude += (long) (1 + e - s) * (e - s) / 2;
            }
        }
        //m长度的区间最终贡献的子数组数量
        return (1 + m) * m / 2 - exclude;
    }

    //p809
    public int expressiveWords(String s, String[] words) {
        int result = 0, n = s.length();
        for (String word : words) {
            int p1 = 0, p2 = 0, m = word.length();
            boolean stretchable = true;
            while (p1 < n && p2 < m) {
                char ch1 = s.charAt(p1);
                char ch2 = word.charAt(p2);
                if (ch1 != ch2) {
                    stretchable = false;
                    break;
                }
                //统计相同字符在各自单词中的数量
                int p1c = 1;
                ++p1;
                while (p1 < n && s.charAt(p1) == ch1) {
                    ++p1c;
                    ++p1;
                }
                int p2c = 1;
                ++p2;
                while (p2 < m && word.charAt(p2) == ch2) {
                    ++p2c;
                    ++p2;
                }
                if ((p1c < p2c) || (p1c != p2c && p1c < 3)) {
                    //在s中太少不行；数量不等时，在s中数量少于3个也不行
                    stretchable = false;
                    break;
                }
            }
            if (p1 < n || p2 < m) {
                stretchable = false;
            }
            if (stretchable) {
                ++result;
            }
        }
        return result;
    }

    //p1023
    public List<Boolean> camelMatch(String[] queries, String pattern) {
        List<Boolean> answer = new ArrayList<>(queries.length);
        for (String query : queries) {
            //i for query index, j for patter index
            int i = 0, j = 0;
            boolean result = true;
            while (i < query.length() && j < pattern.length()) {
                char q = query.charAt(i);
                char p = pattern.charAt(j);
                if (p == q) {
                    ++i;
                    ++j;
                } else {
                    if (Character.isUpperCase(q) && Character.isUpperCase(p)) {
                        result = false;
                        break;
                    }
                    ++i;
                }
            }
            if (result) {
                if (j < pattern.length()) {
                    result = false;
                } else {
                    while (i < query.length()) {
                        if (Character.isUpperCase(query.charAt(i))) {
                            result = false;
                            break;
                        }
                        ++i;
                    }
                }
            }
            answer.add(result);
        }
        return answer;
    }

    //p1616
    public boolean checkPalindromeFormation(String a, String b) {
        //check palindrome for a
        boolean palindrome = true;
        int l = 0, r = a.length() - 1;
        while (l < r) {
            if (a.charAt(l) != a.charAt(r)) {
                palindrome = false;
                break;
            }
            ++l;
            --r;
        }
        if (palindrome) return true;
        //check palindrome for b
        palindrome = true;
        l = 0;
        r = b.length() - 1;
        while (l < r) {
            if (b.charAt(l) != b.charAt(r)) {
                palindrome = false;
                break;
            }
            ++l;
            --r;
        }
        if (palindrome) return true;
        if (a.charAt(0) == b.charAt(b.length() - 1)) {
            //check a prefix, b suffix
            l = 0;
            r = b.length() - 1;
            while (l < r) {
                if (a.charAt(l) != b.charAt(r)) {
                    break;
                }
                ++l;
                --r;
            }
            //switch seq, try b
            int l_ = l, r_ = r;
            while (l_ < r_) {
                if (b.charAt(l_) != b.charAt(r_)) {
                    break;
                }
                ++l_;
                --r_;
            }
            if (l_ >= r_) return true;
            //switch seq, try a
            l_ = l;
            r_ = r;
            while (l_ < r_) {
                if (a.charAt(l_) != a.charAt(r_)) {
                    break;
                }
                ++l_;
                --r_;
            }
            if (l_ >= r_) return true;
        }
        if (b.charAt(0) == a.charAt(a.length() - 1)) {
            //check b prefix, a suffix
            l = 0;
            r = a.length() - 1;
            while (l < r) {
                if (b.charAt(l) != a.charAt(r)) {
                    break;
                }
                ++l;
                --r;
            }
            //switch seq, try b
            int l_ = l, r_ = r;
            while (l_ < r_) {
                if (b.charAt(l_) != b.charAt(r_)) {
                    break;
                }
                ++l_;
                --r_;
            }
            if (l_ >= r_) return true;
            //switch seq, try a
            l_ = l;
            r_ = r;
            while (l_ < r_) {
                if (a.charAt(l_) != a.charAt(r_)) {
                    break;
                }
                ++l_;
                --r_;
            }
            if (l_ >= r_) return true;
        }
        return false;
    }

    //p1662
    public boolean arrayStringsAreEqual(String[] word1, String[] word2) {
        CharScanner cs1 = new CharScanner(word1);
        CharScanner cs2 = new CharScanner(word2);
        Character c1 = cs1.getNextChar();
        Character c2 = cs2.getNextChar();
        while (c1 != null || c2 != null) {
            if (!Objects.equals(c1, c2)) {
                return false;
            }
            c1 = cs1.getNextChar();
            c2 = cs2.getNextChar();
        }
        return true;
    }

    static class CharScanner {
        private final String[] words;
        int wi;
        int ci;

        public CharScanner(String[] words) {
            this.words = words;
            this.wi = 0;
            this.ci = 0;
        }

        Character getNextChar() {
            if (wi >= words.length) {
                return null;
            }
            String word = words[wi];
            Character res = null;
            if (ci < word.length()) {
                res = words[wi].charAt(ci);
            }
            if (ci >= word.length() - 1) {
                ++wi;
                ci = 0;
            } else {
                ++ci;
            }
            return res;
        }
    }

    //p1750
    public int minimumLength(String s) {
        int l = 0, r = s.length() - 1;
        char c0 = s.charAt(l);
        while (r > l && s.charAt(l) == s.charAt(r)) {
            while (l < s.length() && c0 == s.charAt(l)) {
                ++l;
            }
            while (r > -1 && c0 == s.charAt(r)) {
                --r;
            }
            if (l < s.length()) {
                c0 = s.charAt(l);
            }
        }
        return Math.max(0, r - l + 1);
    }

    //p1813
    public boolean areSentencesSimilar(String sentence1, String sentence2) {
        String[] s1 = sentence1.split(" ");
        String[] s2 = sentence2.split(" ");
        return s1.length >= s2.length ? areSentencesSimilar(s1, s2) : areSentencesSimilar(s2, s1);
    }
    private boolean areSentencesSimilar(String[] s1, String[] s2) {
        if (s1.length == s2.length) {
            for (int i = 0; i < s1.length; ++i) {
                if (!s1[i].equals(s2[i])) {
                    return false;
                }
            }
            return true;
        }
        if (s1[0].equals(s2[0]) && s1[s1.length - 1].equals(s2[s2.length - 1])) {
            int i1 = 0, j1 = s1.length - 1, i2 = 0, j2 = s2.length - 1;
            while (i2 < j2) {
                boolean matched = false;
                if (s1[i1].equals(s2[i2])) {
                    matched = true;
                    ++i1;
                    ++i2;
                }
                if (s1[j1].equals(s2[j2])) {
                    matched = true;
                    --j1;
                    --j2;
                }
                if (!matched) {
                    return false;
                }
            }
            return true;
        } else {
            if (s1[0].equals(s2[0])) {
                int i1 = 0, i2 = 0;
                while (i2 < s2.length) {
                    if (!s1[i1].equals(s2[i2])) {
                        return false;
                    }
                    ++i1;
                    ++i2;
                }
                return true;
            } else if (s1[s1.length - 1].equals(s2[s2.length - 1])) {
                int j1 = s1.length - 1, j2 = s2.length - 1;
                while (j2 >= 0) {
                    if (!s1[j1].equals(s2[j2])) {
                        return false;
                    }
                    --j1;
                    --j2;
                }
                return true;
            } else {
                return false;
            }
        }
    }

    /**
     * 2824【排序+双指针】统计和小于目标的下标对数目
     */
    public int countPairs(List<Integer> nums, int target) {
        Integer[] numbers = nums.toArray(new Integer[0]);
        Arrays.sort(numbers);
        int answer = 0, n = numbers.length, l = 0, r = n - 1;
        for (int i = 0; i < n; ++i) {
            while (r > -1 && numbers[l] + numbers[r] >= target) {
                --r;
            }
            if (r < l) break;
            answer += r - l;
            ++l;
        }
        return answer;
    }

    public static void main(String[] args) {
        MultiPointerSolution solution = new MultiPointerSolution();
    }
}
